// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// bitmap.c

// compile with one of
//   gcc -std=c99 -Wall -Wextra -O bitmap.c
//   gcc -std=c99 -Wall -Wextra -O -Dbitmap_64 bitmap.c

// tested on Linux, Mac OS X and Solaris

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// this should be in bitmap.h

// use dynamic allocation with these functions
// compile with -Dbitmap_64 to force 64-bit words
// compile with -O [dash capital o] for more efficient machine code

#ifdef bitmap_64
  #define bitmap_type unsigned long long int
#else	// assumed to be 32 bits
  #define bitmap_type unsigned int
#endif

typedef struct {
  int bits;	// number of bits in the array
  int words;	// number of words in the array
  bitmap_type *array;
} bitmap;

void bitmap_set  (bitmap *b, int n);	// n is a bit index
void bitmap_clear(bitmap *b, int n);
int  bitmap_read (bitmap *b, int n);

bitmap * bitmap_allocate(int bits);
void bitmap_deallocate(bitmap *b);

void bitmap_print(bitmap *b);

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// this should be in bitmap.c

#include <stdio.h>
#include <stdlib.h>

#ifdef bitmap_64
  #define bitmap_type unsigned long long int
  #define bitmap_shift        6
  #define bitmap_mask        63
  #define bitmap_wordlength  64
  #define bitmap_fmt "%016llx"
#else	// assumed to be 32 bits
  #define bitmap_type unsigned int
  #define bitmap_shift        5
  #define bitmap_mask        31
  #define bitmap_wordlength  32
  #define bitmap_fmt "%08x"
#endif

// get the types right
#define bitmap_one        (bitmap_type)1

// we expect 0 <= n and n < b->bits, but it is not verified

void bitmap_set(bitmap *b, int n)
{
  int word = n >> bitmap_shift;		// n / bitmap_wordlength
  int position = n & bitmap_mask;	// n % bitmap_wordlength
  b->array[word] |= bitmap_one << position;
}

void bitmap_clear(bitmap *b, int n)
{
  int word = n >> bitmap_shift;         // n / bitmap_wordlength
  int position = n & bitmap_mask;       // n % bitmap_wordlength
  b->array[word] &= ~(bitmap_one << position);
}

int  bitmap_read(bitmap *b, int n)
{
  int word = n >> bitmap_shift;         // n / bitmap_wordlength
  int position = n & bitmap_mask;       // n % bitmap_wordlength
  return (b->array[word] >> position) & 1;
}

bitmap * bitmap_allocate(int bits)
{
  // error-checking should be better :-)
  bitmap *b = malloc(sizeof(bitmap));
  b->bits = bits;
  b->words = (bits + bitmap_wordlength - 1) / bitmap_wordlength;
    // divide, but round up for the ceiling
  b->array = calloc(b->words, sizeof(bitmap_type));
  return b;
}

void bitmap_deallocate(bitmap *b)
{
  // error-checking should be better :-)
  free(b->array);
  free(b);
}

void bitmap_print(bitmap *b)
{
  for (int i = 0; i < b->words; i++)
    { printf(" " bitmap_fmt, b->array[i]); }
  printf("\n");
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
// this should be in bitmaptest.c

int main(void)
{
  printf("sizeof(bitmap_type) = %zd\n", sizeof(bitmap_type));

  const int testlen = 250;	// number of bits in the bitmap
  bitmap *B = bitmap_allocate(testlen);

  for (int i = 0; i < bitmap_wordlength; i++) { printf("%d", bitmap_read(B, i)); }  printf("\n");
  for (int i = 0; i < bitmap_wordlength; i++) { bitmap_set(B, i); }
  for (int i = 0; i < bitmap_wordlength; i++) { printf("%d", bitmap_read(B, i)); }  printf("\n");
  for (int i = 0; i < bitmap_wordlength; i++) { bitmap_clear(B, i); }
  for (int i = 0; i < bitmap_wordlength; i++) { printf("%d", bitmap_read(B, i)); }  printf("\n");

  bitmap_print(B);
  for (int i = 0; i < testlen; i += 4) { bitmap_set(B, i); }
  bitmap_print(B);
  for (int i = 0; i < testlen; i += 4) { bitmap_set(B, i); }
  bitmap_print(B);
  for (int i = 0; i < testlen; i += 4) { bitmap_set(B, i+1); }
  bitmap_print(B);
  for (int i = 0; i < testlen; i += 4) { bitmap_set(B, i+2); }
  bitmap_print(B);
  for (int i = 0; i < testlen; i += 4) { bitmap_set(B, i+3); }
  bitmap_print(B);
  for (int i = 0; i < testlen; i += 4) { bitmap_clear(B, i+2); }
  bitmap_print(B);
  for (int i = 0; i < testlen; i += 4) { bitmap_clear(B, i); }
  bitmap_print(B);

  bitmap_deallocate(B);
  B = NULL;	// no dangling pointers!

  return 0;
}

